# LeetCode 327.区间和的个数
# https://leetcode.cn/problems/count-of-range-sum/description/

from typing import List
from sortedcontainers import SortedList


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        sum_ = 0
        result = 0
        sums_sort = SortedList()

        for index, num in enumerate(nums):
            sums_sort.add(sum_)
            sum_ += num
            sum_1_upper = sum_ - lower
            sum_1_lower = sum_ - upper

            left_index = sums_sort.bisect_left(sum_1_lower)
            right_index = sums_sort.bisect_right(sum_1_upper)

            result += right_index - left_index

        return result


# 对拍 暴力 超时
# class Solution:
#     def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
#         result = 0
#         for index, num_0 in enumerate(nums):
#             sum_ = 0
#             for j in range(index, len(nums)):
#                 num_1 = nums[j]
#                 sum_ += num_1
#                 if lower <= sum_ <= upper:
#                     result += 1
#
#         return result


if __name__ == '__main__':
    nums = [-2,5,-1]
    lower = -2
    upper = 2

    # nums = [0]
    # lower = 0
    # upper = 0
    # #
    # nums = [-1, 1]
    # lower = 0
    # upper = 0

    nums = [0, -3, -3, 1, 1, 2]
    lower = 3
    upper = 5
    result = Solution().countRangeSum(nums, lower, upper)
    print(result)